package com.LeetCode;
class ListNode {
	int val;
	ListNode next = null;

	ListNode(int x) {
		val = x;
	}
}

// 双指针思想
public class _19_main {
	public static ListNode removeNthFromEnd(ListNode head, int n) {
		if (head == null) {
			return null;
		}
		ListNode left = head;
		ListNode right = head;
		ListNode pre = head;
		int max = 0;
		while (max != n - 1) {
			right = right.next;
			max++;
		}
		if (right.next == null) {
			head = left.next;
			return head;
		}
		while (right.next != null) {
			pre = left;
			left = left.next;
			right = right.next;
		}
		pre.next = left.next;
		return head;
	}

	public static void look(ListNode head) {
		ListNode left = head;
		System.out.println();
		while (left != null) {
			System.out.print(left.val + "->");
			left = left.next;
		}
	}

	public static void main(String[] args) {
		ListNode l1 = new ListNode(1);
		ListNode l2 = new ListNode(2);
		l1.next = l2;
		ListNode l3 = new ListNode(3);
		l2.next = l3;
		ListNode l4 = new ListNode(4);
		l3.next = l4;
		ListNode l5 = new ListNode(5);
		l4.next = l5;
		l5.next = null;
		look(removeNthFromEnd(l1, 2));
	}
}
